package com.ryujung.dp.leetCode_486;

/*
 * @lc app=leetcode.cn id=486 lang=java
 *
 * [486] 预测赢家
 *
 * https://leetcode-cn.com/problems/predict-the-winner/description/
 *
 * algorithms
 * Medium (51.62%)
 * Likes:    147
 * Dislikes: 0
 * Total Accepted:    6.7K
 * Total Submissions: 12.9K
 * Testcase Example:  '[1,5,2]'
 *
 * 给定一个表示分数的非负整数数组。
 * 玩家1从数组任意一端拿取一个分数，随后玩家2继续从剩余数组任意一端拿取分数，然后玩家1拿，……。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
 * 
 * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
 * 
 * 示例 1:
 * 
 * 
 * 输入: [1, 5, 2]
 * 输出: False
 * 解释: 一开始，玩家1可以从1和2中进行选择。
 * 如果他选择2（或者1），那么玩家2可以从1（或者2）和5中进行选择。如果玩家2选择了5，那么玩家1则只剩下1（或者2）可选。
 * 所以，玩家1的最终分数为 1 + 2 = 3，而玩家2为 5。
 * 因此，玩家1永远不会成为赢家，返回 False。
 * 
 * 
 * 示例 2:
 * 
 * 
 * 输入: [1, 5, 233, 7]
 * 输出: True
 * 解释: 玩家1一开始选择1。然后玩家2必须从5和7中进行选择。无论玩家2选择了哪个，玩家1都可以选择233。
 * 最终，玩家1（234分）比玩家2（12分）获得更多的分数，所以返回 True，表示玩家1可以成为赢家。
 * 
 * 
 * 注意:
 * 
 * 1 <= 给定的数组长度 <= 20.
 * 数组里所有分数都为非负数且不会大于10000000。
 * 如果最终两个玩家的分数相等，那么玩家1仍为赢家。
 */
// @lc code=start
class Solution {
    /**
     * 动态规划算法,创建dp数组,dp[i][j]表示在nums[i~j]范围内游戏,
     * 先手玩家高于后手玩家的分数
     * 1,当i=j时,先手玩家才有分数,所以dp[i][j] = nums[i]
     * 2,i!=j时,先手可以选择num[i]或num[j],对应后手dp[i-1][j]或dp[i][j-1]
     */
    public boolean PredictTheWinner(int[] nums) {
        int l = nums.length;
        int[][] dp = new int[l][l];

        for (int i = 0; i < l; i++) {
            dp[i][i] = nums[i];
        }

        for (int i = l - 2; i >= 0; i--) {
            for (int j = i + 1; j <= l - 1; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }

        //nums[0~l-1]范围内先手玩家的领先分数>=0即为胜利者
        return dp[0][l - 1] >= 0;
    }

    /**
     * 递归解法: 85ms
     */
    public boolean PredictTheWinner2(int[] nums) {
        int s1 = bestChiose(0, nums.length - 1, nums, 1);

        return s1 >= 0;
    }

    public int bestChiose(int start, int end, int[] nums, int who) {
        if (start == end) {
            return nums[start];
        }

        //who 值为-1 或 +1 , +1代表玩家1回合,要加上所选择的数;
        // -1代表玩家2回合,要减去选择的数
        int left = who * nums[start] + bestChiose(start + 1, end, nums, -who);
        int right = who * nums[end] + bestChiose(start, end - 1, nums, -who);

        int res = Math.max(left * who, right * who) * who;

        return res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();

        int[] nums = { 5, 233, 7 };
        System.out.println(s.PredictTheWinner(nums));
    }
}
// @lc code=end
